package com.caoyanan.algorithm.question.zuoTraining.training004.class01;

/**
 * 给定一个二维数组matrix，可以从任何位置出发，每一步可以走向上、下、左、右，四个方向。返回最大递增链的长度。
 * 例子：
 * matrix =
 * 5  4  3
 * 3  1  2
 * 2  1  3
 * 从最中心的1出发，是可以走出1 2 3 4 5的链的，而且这是最长的递增链。所以返回长度5
 * @author: caoyanan
 * @time: 2021/5/28 5:29 下午
 */
public class Question05_MatrixMaxLink {

    public static void main(String[] args) {
        int[][] arr = new int[][]{new int[]{5, 4, 3}, new int[]{3, 1, 2}, new int[]{2, 1, 3}};
        int maxLength = maxPath(arr);
        System.out.println(maxLength);
    }

    /**
     * 求二维矩阵上的最长递增链，首先可能是从任意位置触发，
     * 然后交给递归去跑，且可以使用记忆化搜索，即使用一个dp傻缓存。
     * 没有办法改成动态规划，因为它依赖的位置太乱了，每个位置依赖上下左右，左边一个位置又依赖上下左右，依赖循环了。
     * 所以这个递归加记忆化搜索就是最优解法
     * @param arr
     * @return
     */
    private static int maxPath(int[][] arr) {

        int[][] dp = new int[arr.length][arr[0].length];

        int result = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                result = Math.max(result, process(arr, i, j, dp));
            }
        }
        return result;
    }

    /**
     * 递归含义： 给输入的矩阵arr，当前的位置是i，j，缓存数组为dp。
     * 求从i，j出发的最长递增链长度是多少
     * @param arr
     * @param i
     * @param j
     * @param dp
     * @return
     */
    private static int process(int[][] arr, int i, int j, int[][] dp) {

        if (dp[i][j] != 0) {
            return dp[i][j];
        }
        // 向左可以走多少步
        int left = 0;
        if (j > 0 && arr[i][j - 1] > arr[i][j]) {
            left = process(arr, i, j - 1, dp);
        }
        // 向右可以走多少步
        int right= 0;
        if (j < arr[i].length-1 && arr[i][j + 1] > arr[i][j]) {
            right = process(arr, i, j + 1, dp);
        }
        // 向上可以走多少步
        int up = 0;
        if (i > 0 && arr[i - 1][j] > arr[i][j]) {
            up = process(arr, i - 1, j, dp);
        }
        // 向下可以走多少步
        int down = 0;
        if (i < arr.length - 1 && arr[i + 1][j] > arr[i][j]) {
            down = process(arr, i + 1, j, dp);
        }

        // 当前算一步
        dp[i][j] = 1 + Math.max(Math.max(left, right), Math.max(up, down));
        return dp[i][j];
    }
}
